【题解】 [SCOI2007]蜥蜴 网络流 luogu2472 | Qiuly's blog!

【题解】 [SCOI2007]蜥蜴 网络流 luogu2472

Posted on | Edited on | In | Comments:

网络流……..题目要求我们求出能逃离的蜥蜴数量的最大值，不就是最大流吗？

然后考虑怎么建模。

首先来看看蜥蜴，我们将这些蜥蜴的点跟 $s$ 连边，边权是多少呢？想一想，由于一个位置只有一只蜥蜴，那么边权就当然是 $1$ 了。

然后考虑逃离的这些柱子，题目说什么石柱都不稳定，每次当蜥蜴跳跃时，所离开的石柱高度减 $1$ ，看似很不好办，但是这恰恰就是网络流。对于柱子间的一条边，从 $s$ 经过蜥蜴的点的时候，流量就只有 $1$ 了，这个 $1$ 的流量流过柱子中的边的时候就会让这条边的边权减 $1$ ，减到 $0$ 当然就不能流了。

那么柱子之间怎么连边呢？

对于一个柱子，我们将它拆成两个点，一个入点，一个出点。其中入点向出点连一条边，边权为这个柱子的高度。如果一个柱子，判断一下，发现从它这里可以跳出去，那么就将这个柱子的出点向 $t$ 连一条边，这条边仅仅是代表找到了答案，对答案没有影响，边权为 $inf$ 。

然后我们再看一下，这个柱子能到达的柱子有哪些，这里直接算曼哈顿距离就好了。然后由这条柱子的出点向能到达的柱子的入点连一条边，边权呢？还是为 $inf$ 。因为我们对一个柱子的影响就是入点到出点的那一条边，那一条边的边权已经限制了这个柱子的使用量，所以中间的边权为 $inf$ 。

注意数组大小，要开大一点。

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/*
---[SCOI2007]蜥蜴.网络流-最大流   毒瘤题目
*/
#include<queue>
#include<vector>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>

#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)<(y)?(x):(y))
#define ID(ty,x,y) ((ty)*r*c+id[(x)][(y)])

const int N=55;
const int S=1e5+2;
const int inf=1e9+9;

std::queue<int> q;
std::vector<std::pair<int,int> > lizard;
std::vector<std::pair<int,int> > Pillar;
int r,c,d,s,t;
int dep[S],head[S],cnt=1;
int val[N][N],id[N][N],tot=0,total=0;
char str;
struct Edge{int nxt,to,val;}G[N*N*8];

inline void add(int u,int v,int w){
    G[++cnt].nxt=head[u],G[cnt].to=v,G[cnt].val=w,head[u]=cnt;
    G[++cnt].nxt=head[v],G[cnt].to=u,G[cnt].val=0,head[v]=cnt;
}

template <typename _Tp> inline void IN(_Tp&x){
    char ch;bool flag=0;x=0;
    while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
    while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
    if(flag)x=-x;
}

int bfs(){
    std::memset(dep,0,sizeof(dep));
    dep[s]=1;q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=head[u];i;i=G[i].nxt){
            int v=G[i].to;
            if(!dep[v]&&G[i].val>0)
                dep[v]=dep[u]+1,q.push(v);   
        }
    }return dep[t];
}

int dfs(int u,int flow){
    if(u==t||!flow)return flow;
    int used=0,rlow;
    for(int i=head[u];i;i=G[i].nxt){
        int v=G[i].to;
        if(dep[v]==dep[u]+1&&G[i].val>0){
            used+=(rlow=dfs(v,min(G[i].val,flow-used)));
            G[i].val-=rlow,G[i^1].val+=rlow;
        }
    }if(!used)dep[u]=-1;
    return used;
}

int dinic(){
    int maxflow=0;
    while(bfs())maxflow+=dfs(s,inf);
    return maxflow;
}

void _pre_in(){
    IN(r),IN(c),IN(d);
    s=0,t=r*c*2+1;
    Pillar.clear();//柱子
    lizard.clear();//蜥蜴
    for(int i=1;i<=r;++i)
        for(int j=1;j<=c;++j){
            std::cin>>str;
            id[i][j]=++tot,val[i][j]=str-'0';
            if(val[i][j]>0)Pillar.push_back(std::make_pair(i,j));
        }
    for(int i=1;i<=r;++i)
        for(int j=1;j<=c;++j){
            std::cin>>str;
            if(str=='L')++total,lizard.push_back(std::make_pair(i,j));
        }
    return;
}

void _pre_add_line(){//连边
    for(int i=0;i<Pillar.size();++i){
        int x=Pillar[i].first,y=Pillar[i].second;
        add(ID(0,x,y),ID(1,x,y),val[x][y]);
        if(x<=d||y<=d||x+d>r||y+d>c)add(ID(1,x,y),t,inf);//可以逃出去
    }
    for(int i=0;i<Pillar.size();++i)
        for(int j=0;j<Pillar.size();++j){
            if(i==j)continue;
            int xi=Pillar[i].first,yi=Pillar[i].second;
            int xj=Pillar[j].first,yj=Pillar[j].second;
            if((xi-xj)*(xi-xj)+(yi-yj)*(yi-yj)<=d*d)
                add(ID(1,xi,yi),ID(0,xj,yj),inf);//柱子之间可以互相到达
        }
    for(int i=0;i<lizard.size();++i){
        int x=lizard[i].first,y=lizard[i].second;
        add(s,ID(0,x,y),1);//源点向蜥蜴连边
    }return;
}

int main(){
    _pre_in();
    _pre_add_line();
    printf("%d\n",total-dinic());
    /*注意最终要算的是最少的未逃离的数，不是逃离的最大数*/
    return 0;
}

本文标题:【题解】 [SCOI2007]蜥蜴 网络流 luogu2472

文章作者:Qiuly

发布时间:2019年03月06日 - 00:00

最后更新:2019年03月29日 - 13:53

原始链接:http://qiulyblog.github.io/2019/03/06/[题解]luoguP2472/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。